Ковер Серпинского

Перед вами — ковер Серпинского, это типичный пример фрактальной фигуры. Как и для абсолютного большинства фракталов, ему присуще свойство самоподобия: если мы рассмотрим небольшой фрагмент ковра Серпинского в увеличенном масштабе, то это, в отличие от обычных фигур, не приведет к упрощению рисунка: напротив, откроется столь же сложная картина, что была сначала.

Ковер Серпинского, как и многие другие фракталы, строится итеративно (по шагам) следующим образом. В качестве начального объекта берется квадрат. На первом шаге нужно мысленно разбить этот квадрат на 9 равных квадратиков, а затем (уже не мысленно, а вполне реально) удалить центральный из них (рис. 1, можно не удалять центральный квадрат, а перекрашивать его, если вам так больше нравится). На втором шаге каждый из оставшихся восьми квадратиков также надо мысленно разделить на 9 равных квадратиков, после чего удалить центральный из них. На третьем шаге та же самая операция проводится с каждым из 64 оставшихся квадратиков и так далее до бесконечности. То, что остается в итоге, после завершения этой бесконечной процедуры, и называется ковром Серпинского (этим на первый взгляд парадоксальным словам легко придать строгий смысл: ковер Серпинского состоит из всех точек исходного квадрата, которые не будут вырезаны из него ни на каком из шагов описанной процедуры).

Рис. 1. Первые три шага построения ковра Серпинского

Построенная таким образом фигура обладает рядом интересных и довольно неожиданных свойств. Во-первых, ее площадь равна нулю. В самом деле, пусть, для определенности, длина стороны исходного квадрата равна единице. Тогда:

• на первом шаге выкидывается квадрат, площадь которого равна \(\frac{1}{3^2}\);
• на втором шаге выкидываются 8 квадратов, площадь каждого из которых равна \(\frac{1}{9^2}\);
• на третьем шаге выкидываются \(8^2=64\) квадратика, площадь каждого из которых равна \(\frac{1}{27^2}\);
• ...

Легко видеть, что площади вырезаемых частей образуют геометрическую прогрессию с начальным членом \({1}/{9}\) и частным \({8}/{9}\). Поэтому, суммируя, мы обнаруживаем, что, шаг за шагом выкидывая все больше квадратиков, в конце концов мы вырежем бесконечно много кусков, общая площадь которых составит

То есть останется фигура площади \(1-1=0\). Этот же факт можно объяснить еще вот как: площадь оставшейся фигуры на первом шаге равна \({8}/{9}\), на втором — \(\left({8}/{9}\right)^2\), ... На n-м шаге площадь оставшегося куска составит \(\left({8}/{9}\right)^n\), и понятно, что при \(n\to\infty\) эта площадь стремится к нулю.

Таким образом, ковер Серпинского нельзя в полной мере считать плоской фигурой — такие фигуры обычно имеют ненулевую площадь. С другой стороны, кажется интуитивно понятным (и это правда), что он не относится и к семейству кривых, занимая как бы промежуточное положение. Более того, размерность ковра Серпинского оказывается дробной. Об этом читайте в задаче Разные размерности.

Рис. 2.

Как видно из процесса построения, ковер Серпинского является самоподобной фигурой, то есть его можно разбить на несколько частей, каждая из которых подобна исходной фигуре — на этом наблюдении основывается вычисление ее фрактальной размерности в задаче. Это значит, что к нему, как и к любой самоподобной фигуре, можно применить процесс дефляции-инфляции (см.: Самоподобные замощения). Именно, мы можем разбить ковер Серпинского на восемь ковриков меньшего размера, а затем «раздуть» их в три раза так, чтобы в итоге каждый из этих ковриков сравнялся по размеру с исходной фигурой. Затем опять разбить каждую из частей на 8 ковриков, «раздуть» их до размеров исходного ковра и так далее. Продолжая этот процесс до бесконечности, в пределе мы придем к «замощению» всей плоскости коврами Серпинского (рис. 2). Его можно мыслить, как объединение одного бесконечного дырявого ковра — настолько дырявого, что он занимает нулевую площадь, — и бесконечного набора квадратных заплаток, которыми в этом ковре заполнены все дырки.

Рис. 3.

Полученное «замощение» обладает как свойствами, типичными для самоподобных замощений, так и свойствами, присущими фрактальным конструкциям. Прежде всего, оно иерархично. Каждый уровень иерархии соответствует некоторой фиксированной длине r, представляющей собой целую степень тройки (\(r=3^n\), где \(n\in\mathbb{Z}\)), и фактически вся плоскость разбивается на копии ковра Серпинского со стороной r и «вырезанных» квадратов-заплаток со стороной r (рис. 3). При этом переход на следующий уровень осуществляется разбиением каждого ковра Серпинского на 8 ковриков и 1 заплатку, а каждой заплатки — на 9 квадратов-заплаток меньшего размера, в то время как переход на предыдущий уровень происходит благодаря объединению 8 ковров и 1 заплатки в мегаковер или 9 заплаток в одну мегазаплатку соответственно.

Рис. 4.

Описанная выше иерархия является строгой в том смысле, что переход с одного уровня на другой может быть произведен единственно возможным способом. Это означает, что для каждого коврика данного уровня иерархии однозначно определена позиция, в которой он входит в ковер предыдущего уровня, — это одна из восьми позиций, показанных на рис. 4. Аналогично, каждая заплатка входит либо в ковер предыдущего уровня на центральной позиции, либо в заплатку предыдущего уровня в одной из 9 позиций.

Как и для любого самоподобного замощения, отсюда следует, что наша картинка является непериодической. Иными словами, ни при каком параллельном переносе ее нельзя совместить с собой. В самом деле, в описанном «замощении» встречаются заплатки размера \(3^n\times3^n\) для всех натуральных чисел n. В частности, это означает, что какой бы параллельный перенос мы ни рассмотрели, найдется настолько огромная заплатка, что при этом параллельном переносе она наложится сама на себя, а значит, о самосовмещении не может быть и речи. С другой стороны, практически любой конечный фрагмент этой картинки встретится в ней бесконечно много раз. В самом деле, укрупняя картинку, то есть переходя к предыдущему уровню достаточное число раз, можно добиться того, чтобы искомый фрагмент целиком оказался лежащим внутри некоторого ковра Серпинского размера r. А это значит, что в любом ковре того же размера этот же фрагмент обязательно встретится. Более того, отсюда следует еще одно свойство этого «замощения», типичное для всех фрактальных конструкций: если рассмотреть небольшой его фрагмент в крупном масштабе, то его поведение будет похоже на поведение всей конструкции в целом.

Наконец, аналогично самоподобным замощениям многоугольниками, каждому «замощению» бесконечным ковром Серпинского и набором квадратных заплаток можно сопоставить семейство последовательностей целых чисел. Именно, возьмем произвольный ковер Серпинского A размера 1 и посмотрим, на какой из позиций с рис. 4 он входит в мегаковер — это будет первый элемент последовательности. Затем поглядим, на какой из позиций мегаковер входит в супермегаковер — это будет второй элемент. Продолжая в том же духе, в итоге получим некоторую последовательность \((\alpha_n)\), составленную из целых чисел от 1 до 8. Если бы мы взяли другой ковер Серпинского B в качестве стартовой точки, мы бы получили другую последовательность, однако ее отличие от \((\alpha_n)\) заключалось бы только в конечном числе k начальных символов, поскольку для некоторого k существует ковер k-го уровня, который содержит как ковер A, так и ковер B. С другой стороны, мы могли бы начать с ковра размера 3, содержащего A, или с ковра размера 1/3, содержащегося в A — так мы бы получили последовательность, которая отличается от \((\alpha_n)\) стиранием или добавлением одной цифры соответственно. Как бы то ни было, в данном «замощении» различных ковров Серпинского (в том числе, ковров разных размеров) счетное число, а различных последовательностей из целых чисел от 1 до 8 — континуум. С учетом того, что почти любой последовательности сопоставляется «замощение» плоскости, мы можем заключить, что различных «замощений» континуум. (Существуют исключительные последовательности, которым соответствуют замощения не всей плоскости, а только ее части. Например, последовательность 111111... сопоставляется «замощению» четверти плоскости, а последовательность 131313... — «замощению» полуплоскости; однако вероятность того, что случайно выбранная последовательность окажется исключительной, равна нулю.)

Конструкцию ковра Серпинского легко обобщить на другие фигуры. Если использовать окружности вместо квадратов, то получится так называемая сетка Аполлония. А на рис. 5 показано, что получится, если использовать равносторонний треугольник и шестиугольник (примечательно, что для первого шестиугольника предельное множество получается таким же, как и для треугольника, — с точностью до поворота на \(30^{\circ}\) вокруг центра, а для второго граница искомого множества представляет собой еще один фрактал — снежинку Коха).

Рис. 5.

Часто она возникает в других математических задачах, на первый взгляд не связанных с самоподобием и фракталами. Рассмотрим, например, знаменитый треугольник Паскаля, составленный из натуральных чисел согласно следующему правилу: в его n-й строке стоит ровно n чисел, крайние из которых равны 1, а каждое из промежуточных представляет собой сумму двух чисел из предыдущей строки, стоящих прямо над ним слева и справа. Оказывается, если мы раскрасим четные числа треугольника Паскаля одним цветом, а нечетные — другим, получится в точности треугольный ковер Серпинского (рис. 6).

Рис. 6.

Еще один пример возникает в теории клеточных автоматов. Одномерный клеточный автомат представляет собой бесконечную ленту, разделенную на клеточки, каждая из которых окрашена в свой цвет. Каждую секунду каждая клетка перекрашивается по некоторому правилу (своему для каждого конкретного автомата) в зависимости от того, какого цвета были ее соседи в предыдущий момент времени.

Рис. 7.

Например, клетки автомата, изображенного на рис. 7, раскрашены в два цвета, и на каждом следующем шаге каждая клетка обращается в тот цвет, которым окрашено большинство из ее ближайших соседей, включая ее саму (в этом примере мы предполагаем, что все клетки слева и справа от изображенного куска ленты являются голубыми). Количество цветов, а также количество соседей, влияющих на перекрашивание, вообще говоря, может отличаться для разных клеточных автоматов. В простейшем случае, как в ситуации, упомянутой выше, встречаются клетки только двух цветов, а непосредственное влияние оказывают только соседи, смежные с данной клеткой.

Прикладывая друг к другу ленты, соответствующие состояниям, в которых находился данный автомат в различные моменты времени, мы можем наблюдать динамику процесса. Оказывается, нетрудно придумать автомат, для которого получающаяся картинка при подходящих начальных условиях представляет собой в точности треугольник Серпинского. Действительно, для этого достаточно взять автомат, клетки которого раскрашены в два цвета, и в любой момент времени клетка окрашивается в первый цвет в том и только в том случае, если ровно один из двух ее ближайших соседей имел первый цвет на предыдущем шаге. Остается взять в качестве начального состояния ленту, ровно одна клетка которой покрашена в первый цвет (рис. 8).

Рис. 8.

Напоследок отметим, что аналогичные конструкции можно соорудить и в пространстве. В зависимости от того, какую именно фигуру мы возьмем в качестве исходной и как именно будем разбивать ее на части, будут получаться различные фракталы. Пожалуй, самые известные примеры — губка Менгера, тетраэдр Серпинского (tetrix), канторова пыль (Cantor dust) и иерусалимский куб (Jerusalem cube).

Рисунки © Хайдар Нурлигареев.

Хайдар Нурлигареев